package com.example.algo.lru;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 通过继承 LinkedHashMap 实现 LRU
 * 先进先出，访问过一次之后移动到最后面
 * 例：现在顺序 1 2 3， 访问 1 之后，顺序变为 2 3 1
 */
public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private int cacheSize;


    public LruCache(int cacheSize) {
        /**
         * initialCapacity: 初始容量大小
         * loadFactor: 负载因子
         * accessOrder: false基于插入排序（默认），true基于访问排序
         */
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }


    /**
     * 添加元素之后是否删除最老的元素
     *
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }


    private void print(LruCache<String, String> lru) {
        for (Map.Entry<String, String> entry : lru.entrySet()) {
            System.out.println("key:" + entry.getKey() + "   value:" + entry.getValue());
        }
        System.out.println();
    }


    public static void main(String[] args) {

        LruCache<String, String> lru = new LruCache<>(3);
        lru.put("1", "1");
        lru.put("2", "2");
        lru.put("3", "3");
        // 应该输出 1 2 3
        lru.print(lru);

        // 容器已满
        lru.put("4", "4");
        // 应输出 2 3 4
        lru.print(lru);

        // 访问最后一个元素，访问之后应该添加队列头部
        System.out.println("访问链表最后一个元素 --> " + lru.get("2"));
        // 应输出 3 4 2
        lru.print(lru);

        // 再添加一个
        lru.put("5", "5");
        // 应输出 4 2 5
        lru.print(lru);


    }
}
